package com.njupt.DynamicProgramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/15 22:50
 * @Description: 118. 杨辉三角
 * @Version: 1.0
 */


public class Generate_118 {

    /**
     * 暴力解
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> results = new ArrayList<>();
        results.add(Arrays.asList(1));
        if(numRows == 1){
            return results;
        }
        results.add(Arrays.asList(1,1));
        if(numRows == 2){
            return results;
        }

        for (int i = 3; i <= numRows ; i++) {
            List<Integer> result = new ArrayList<>();
            result.add(1);
            List<Integer> listItr = results.get(i-2);
            for (int j = 0; j < listItr.size()-1; j++) {
                result.add(listItr.get(j) + listItr.get(j+1));
            }
            result.add(1);
            results.add(result);
        }
        return results;
    }

    /**
     * 杨辉三角形 动态规划
     * @param numRows
     * @return
     */
    public List<List<Integer>> generateDp(int numRows) {
        List<List<Integer>> results = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> result = new ArrayList<>();
            for (int j = 0; j <= i ; j++) {
                if(j==0 || j == i){
                    result.add(1);
                }else {
                    result.add(results.get(i-1).get(j-1) + results.get(i-1).get(j));
                }
            }
            results.add(result);
        }



        return results;
    }

    public static void main(String[] args) {
        Generate_118 test = new Generate_118();
        List<List<Integer>> generate = test.generateDp(5);
        System.out.println(generate);

    }
}
